package zd.vrp.initsolution;

import zd.vrp.global.City;
import zd.vrp.global.GlobalInformation;
import zd.vrp.global.Route;

public class SolomonInsertion1 {
	//initialization
	public static Route initRouteByC1(){
		Route newRoute = new Route();
		int insertedCityNum = 0;
		for(int i=GlobalInformation.cityNum-1;i>=0;i--){
			int currentCityIndex = GlobalInformation.ranks[i];
			if(currentCityIndex != 0){
				City currentCity = GlobalInformation.cityList.get(currentCityIndex);
				if(currentCity.getRoute() != null){
					continue;
				}
				
				if(newRoute.checkDemandFeasibility(currentCity)&&newRoute.checkTimeFeasibility(currentCity,newRoute.getLastCityIndex())){
					newRoute.insertCityIntoRoute(currentCity, newRoute.getLastCityIndex());
					insertedCityNum++;
					break;
				}				
			}
		}
		if(insertedCityNum == 0){
			return null;
		}else{
			GlobalInformation.routeList.add(newRoute);
			return newRoute;
		}
	}
	//get last active route
	public static Route getCurrentRoute(){
		int routeSize = GlobalInformation.routeList.size();
		Route currentRoute = null;
		if(routeSize==0){
			currentRoute = initRouteByC1();
		}else{
			currentRoute = GlobalInformation.routeList.get(routeSize-1);
		}
		return currentRoute;
	}
	
	public static InsertionObject chooseInsertPositionFromCurrentRoute(City city){
		InsertionObject io = new InsertionObject();
		io.currentBestCity = city;
		
		Route currentRoute = getCurrentRoute();
		
		//1.1 first check whether this new inserted city satisfies capacity requirement
		if(currentRoute.checkDemandFeasibility(city)==false){
	
			return io;
		}
		//2. for each possible insertion possition
		for(int j=1;j<currentRoute.getCityList().size();j++){
			//2.1 check whether insertion to this position violate time window
			if(currentRoute.checkTimeFeasibility(city, j)==false){
				continue;
			}
			//2.2 calculate c11 and c12
			City previousCity = currentRoute.getCityList().get(j-1);
			City followingCity = currentRoute.getCityList().get(j);
			double c11 = currentRoute.getInsertionDistanceCostSolomonI(city, j);
			double c12 = currentRoute.getStartTimeOfFollowingCityAfterInsertion(city, j)-followingCity.getStartTime();

			double c1 = SolomonParameter.alpha1*c11+SolomonParameter.alpha2*c12;

			//2.3 compare c1 with current best value
			if(c1<io.currentBestInsertionValue){
				io.currentBestInsertionValue = c1;
				io.currentBestRoute = currentRoute;
				io.currentBestPosition = j;					
			}

		}
		return io;
	}
	
	//solomon's insertion heuristics
	//c1. choose least cost insertion position for an unvisited city
	public static InsertionObject chooseInsertionPostionForUnvisitedCity(City city){
	
		InsertionObject io = new InsertionObject();
		io.currentBestCity = city;
				
		//1. iterate each route
		for(int i=0;i<GlobalInformation.routeList.size();i++){
			
			Route currentRoute = GlobalInformation.routeList.get(i);
			
			//1.1 first check whether this new inserted city satisfies capacity requirement
			if(currentRoute.checkDemandFeasibility(city)==false){
				continue;
			}
			//2. for each possible insertion position
			for(int j=1;j<currentRoute.getCityList().size();j++){
				//2.1 check whether insertion to this position violate time window
				if(currentRoute.checkTimeFeasibility(city, j)==false){
					continue;
				}
				//2.2 calculate c11 and c12
				City previousCity = currentRoute.getCityList().get(j-1);
				City followingCity = currentRoute.getCityList().get(j);
				double c11 = currentRoute.getInsertionDistanceCostSolomonI(city, j);
				double c12 = currentRoute.getStartTimeOfFollowingCityAfterInsertion(city, j)-followingCity.getEtime();
				
				double c1 = SolomonParameter.alpha1*c11+SolomonParameter.alpha2*c12;
				
				//2.3 compare c1 with current best value
				if(c1<io.currentBestInsertionValue){
					io.currentBestInsertionValue = c1;
					io.currentBestRoute = currentRoute;
					io.currentBestPosition = j;					
				}
			}
		}
		return io;
	}
	
	//2. calculate c2
	public static void chooseOptimalCity(){
		InsertionObject io = new InsertionObject();
		io.currentBestInsertionValue = -1000000;
		//2.1 iterate each unvisited city
		for(int i=1;i<GlobalInformation.cityList.size();i++){
			
			City currentCity = GlobalInformation.cityList.get(i);
						
			//2.1.1 check whether this city is unvisited
			
			if(currentCity.getRoute() != null){
				continue;
			}
			//2.1.2 choose best insertion position for this city
			//InsertionObject newIO = chooseInsertionPostionForUnvisitedCity(currentCity);

			InsertionObject newIO = chooseInsertPositionFromCurrentRoute(currentCity);
			//2.1.3 check whether any feasible insertion exists
			if(newIO.currentBestRoute == null){				
				continue;
			}
			
			double c2 = SolomonParameter.lamda*GlobalInformation.distance[currentCity.getId()]-newIO.currentBestInsertionValue;
			newIO.currentBestInsertionValue = c2;		
			//2.1.4 if this insertion is better than current one, replace it
			if(newIO.currentBestInsertionValue > io.currentBestInsertionValue){
				io.replaceIO(newIO);
			}
		}		
		
		//2.2 if io is not null, execute insertion
		if(io.currentBestRoute != null){
			//System.out.println("insertion city:"+io.currentBestCity.getId()+" insertion position:"+io.currentBestPosition+" time feasibility:"+io.currentBestRoute.checkTimeFeasibility(io.currentBestCity, io.currentBestPosition));
			io.currentBestRoute.insertCityIntoRoute(io.currentBestCity, io.currentBestPosition);
			
		}else{
			initRouteByC1();
		}
	}
}
